/*
 * This is the associated tree data structure.
 * In Range Tree, the second level of data structure is also a BST,
 * constructed according to their y-coordinates.
 * This class is also a subclass of RBTree.
 */

package MyAssoTree;

import java.awt.Point;
import java.util.ArrayList;

import Red_Black_Tree.RBTree;

public class MyAssoTree extends RBTree {

	public MyAssoTree (){
		super();
		
		leaf = new MyAssoNode();
		leaf.setLeaf();
		leaf.setBlack();
	}
	
	public void query (int ymin, int ymax, ArrayList<Point> report) {
		ArrayList<MyAssoNode> leftPath = getPath(ymin);
		ArrayList<MyAssoNode> rightPath = getPath(ymax);
		
		int i = 0;
		for(i = 0; i < Math.min(leftPath.size(), rightPath.size()); i++) {
			if(!leftPath.get(i).equals(rightPath.get(i)))
				break;
		}
		
		// Test two paths
		for(MyAssoNode n : leftPath) {
			if (n.getY() >= ymin && n.getY() <= ymax)
				report.add(new Point(n.getX(), n.getY()));
		}
		for(int j = i; j < rightPath.size(); j++){
			int y = rightPath.get(j).getY();
			if(y >= ymin && y <= ymax)
				report.add(new Point(rightPath.get(j).getX(), rightPath.get(j).getY()));
		}
		
		// Then report points between these two paths
		for (int j = i; j < leftPath.size(); j++){
			MyAssoNode n = leftPath.get(j);
			if(ymin <= n.getY() && !n.getRChild().equals(leaf)){
				ArrayList<MyAssoNode> subtree = n.getRSubTree();
				for(MyAssoNode n2 : subtree)
					report.add(new Point(n2.getX(), n2.getY()));
			}
		}
		for (int j = i; j < rightPath.size(); j++){
			MyAssoNode n = rightPath.get(j);
			if(ymax >= n.getY() && !n.getLChild().equals(leaf)){
				ArrayList<MyAssoNode> subtree = n.getLSubTree();
				for(MyAssoNode n2 : subtree)
					report.add(new Point(n2.getX(), n2.getY()));
			}
		}
	}
	
	private ArrayList<MyAssoNode> getPath(int y){
		ArrayList<MyAssoNode> path = new ArrayList<MyAssoNode>();
		MyAssoNode n = (MyAssoNode) root;
		
		while(!n.isLeaf()) {
			path.add(n);
			
			if(y <= n.getY())
				n = (MyAssoNode) n.getLChild();
			else
				n = (MyAssoNode) n.getRChild();
		}
		
		return path;
	}
}
